package demo.practice.tree;

import demo.practice.TreeNode;

public class Offer07 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //前序遍历 preorder = [3,9,20,15,7]
        //中序遍历 inorder = [9,3,15,20,7]
        //前序遍历知道的是当前节点的root，中序遍历划分 当前节点的左右两边

        //1、前序遍历的第一个元素为3，当前节点的root为3。找到中序遍历中的3，则左子树的元素为3，右子树的元素为15，20，7
        //递归的过程有  int[] preorder, int[] inorder, root
        /* int index= 0;TreeNode root= new TreeNode(preorder[index]);*/

        if(preorder.length==0||preorder.length!=inorder.length)
            return null;
        return  buildTree(preorder,  inorder, 0, inorder.length);
    }


    int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder,int preL,int preR){
        //
        if(preL==preR||index==preorder.length ){
            return null;
        }

        int rootval= preorder[index++];
        TreeNode root= new TreeNode(rootval);
        //构造
        //root.left=
        Integer sindex= null;
        for(int i=preL;i<preR;i++){
            if(inorder[i]== rootval ){
                //分割點找到了
                sindex= i;
                break;
            }
        }

        if(sindex==null)
            return root;
        //[9]
        root.left = buildTree(preorder,inorder,preL,sindex);  //1，0，1  ，2
        //[15,20,7]


        root.right = buildTree(preorder,inorder,sindex+1,preR);
        return root;
    }
}